package main;

import java.util.*;

public class EquationSolver {
    public static void main(String[] args) {
        int[] coefficients = {33, 20, 99}; // 转换后的系数
        int target = 130;                   // 转换后的目标值
        solveMaximalSolutions(coefficients, target);
    }

    public static void solveMaximalSolutions(int[] coefficients, int target) {
        // 动态规划表：key为当前总和，value为解的集合
        Map<Integer, List<int[]>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        dp.get(0).add(new int[3]); // 初始解：x'=0, y'=0, z'=0

        // 动态规划填表
        for (int i = 0; i < coefficients.length; i++) {
            int coeff = coefficients[i];
            Map<Integer, List<int[]>> newDp = new HashMap<>();

            for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
                int currentSum = entry.getKey();
                List<int[]> combs = entry.getValue();

                for (int[] comb : combs) {
                    int maxM = (target - 1 - currentSum) / coeff;
                    for (int m = 0; m <= maxM; m++) {
                        int newSum = currentSum + m * coeff;
                        int[] newComb = Arrays.copyOf(comb, 3);
                        newComb[i] += m;

                        if (newSum >= target) continue;

                        newDp.computeIfAbsent(newSum, k -> new ArrayList<>()).add(newComb);
                    }
                }
            }
            dp = newDp;
        }

        // 收集严格小于目标的解
        List<int[]> solutions = new ArrayList<>();
        for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
            if (entry.getKey() < target) {
                solutions.addAll(entry.getValue());
            }
        }

        // 过滤极大解（至少一个变量加1后 ≥ target）
        List<int[]> maximalSolutions = new ArrayList<>();
        for (int[] comb : solutions) {
            boolean isMaximal = false;
            for (int i = 0; i < 3; i++) {
                int tempSum = 0;
                for (int j = 0; j < 3; j++) {
                    tempSum += (j == i) ? coefficients[j] * (comb[j] + 1) : coefficients[j] * comb[j];
                }
                if (tempSum >= target) {
                    isMaximal = true;
                    break;
                }
            }
            if (isMaximal) maximalSolutions.add(comb);
        }

        // 输出结果
        if (maximalSolutions.isEmpty()) {
            System.out.println("无满足条件的解");
        } else {
            System.out.println("满足条件的解（共 " + maximalSolutions.size() + " 种）：");
            for (int[] comb : maximalSolutions) {
                int x = comb[0] + 7; // 恢复原始变量
                int y = comb[1] + 10;
                int z = comb[2] + 1;
                System.out.printf("x=%d, y=%d, z=%d\n", x, y, z);
            }
        }
    }
}
